import javax.print.attribute.standard.PagesPerMinute;
import java.lang.reflect.ParameterizedType;
import java.util.*;

/**
 * 哈希桶的模拟实现
 */
public class MyHashMap<K,E> {

    private ListNode[] listNodes;//节点数组
    private int size ;//元素个数
    private static double CONFLICT_FACTOR = 0.75;//冲突因子

   //节点类
    public static class ListNode<K,E>{
        K key;
        E val;
        ListNode next;

        public ListNode(K key,E val){
            this.key = key;
            this.val = val;
        }
   }

   //默认初始化
   public MyHashMap(){
        listNodes = new ListNode[8];
        size = 0;
   }
   //指定参数初始化
    public MyHashMap(int Initial){
        listNodes = new ListNode[Initial];
        size = 0;
    }

    /**
     * put方法的实现
     * @param key  键值
     * @param val  元素
     */
    public boolean put(K key,E val){

        //1.获取下标
        int tem = 0;
        if(key instanceof Integer){
            tem = (int) key;//向下转型
        }else
            throw new ClassCastException();;//需要是Integer才可计算

        //如果是其它类型如String Character就需要其它的哈希函数计算，
        // 在原有的if - else语句基础上加上更多判断条件，此处就不实现！

        int index = (tem + listNodes.length) % listNodes.length;//防止负数取余操作，下标为负数

        //2.查找数组中index下标是否已有节点
        //第一种情况：存在节点——》判断该节点对应的链表将中是否存在相同键值的元素
        //如果存在就将val值替换
        for(ListNode<K,E> cur = listNodes[index];cur != null;cur =cur.next){
            //查找到当前中间的key值存在，替换val
            if(key == cur.key){
                cur.val = val;//完成替换
                return true;//增加成功
            }
        }

        //第二种情况，index下标 对应节点中不存在，需要重新添加一个节点，或者节点中没有
        //key的键值，也需要重新创建一个节点
        //使用头插法插入
        ListNode<K,E> newNode = new ListNode<>(key,val);
        newNode.next = listNodes[index];//新节点的下一个节点是当前的头节点
        listNodes[index] = newNode;//当前的头节点更新为新的节点

        //判断是否需要扩容，若需要扩容调用resize函数
        if(isExpansion()) resize();

        return true;
    }

    private boolean isExpansion(){
        return ((1.0 * size) /  listNodes.length) >= CONFLICT_FACTOR;
    }

    private void resize(){
        //1.采取二倍扩容的机制
        ListNode[] newlistNodes = new ListNode[listNodes.length * 2];

        //2.将原来的数据拷贝到新的数组中，需要重新计算index
        //遍历原有数组，查找不为空的节点
        for(int i = 0;i < listNodes.length;i++){
            ListNode<K,E> cur = listNodes[i];
            //链表不为空，将链表重新分配到新的数组中
            while(cur != null){
                //计算index
                int index = -1,key = -1;
                if(cur.key instanceof Integer){
                    key = (int)cur.key;
                }else throw new ClassCastException();//类型不兼容异常

                index = (key + newlistNodes.length) % newlistNodes.length;

                ListNode<K,E> curN = cur.next;//保存当前节点的下一个节点
                //此时原数组中的元素key都是唯一的，不存在需要替换val值
                //不需要考虑第一种情况，使用上面第二种情况即可
                curN = newlistNodes[index];//当前节点的下一个节点是插入链表的头节点
                newlistNodes[index] = cur;//更新头节点
                cur = curN;//判断原有链表是否还存在其它节点
            }

            //两层循环把表的节点全部重新分配到新的数组中，将新数组的引用赋值给原数组，完成扩容
            listNodes = newlistNodes;
        }
    }

    public E get(K key){
        //1.计算index
        int index = 0,k = 0;
        if(key instanceof Integer){
            k = (int)key;
        }else throw new ClassCastException();
        index = (listNodes.length + k) % listNodes.length;

        //2.遍历链表
        ListNode<K,E> cur = listNodes[index];

        while(cur != null){
            if(cur.key == key) return cur.val;
            ListNode<K,E> curN = cur.next;
            cur = curN;
        }

        //3，找不到，抛异常
        throw new NullPointerException();
    }

    private int get_index(K key){
        int k = 0;
        if(key instanceof Integer){
            k = (int)key;
        }else throw new ClassCastException();

        return (listNodes.length + k) % listNodes.length;
    }

    public E getOrDefault(K key,E def){
        //1.计算index
        int index = 0,k = 0;
        if(key instanceof Integer){
            k = (int)key;
        }else throw new ClassCastException();

        index = (listNodes.length + k) % listNodes.length;

        //2.遍历链表
        ListNode<K,E> cur = listNodes[index];

        while(cur != null){
            if(cur.key == key) return cur.val;
            ListNode<K,E> curN = cur.next;
            cur = curN;
        }

        //3，找不到，抛异常
        return def;
    }

    public boolean containsKey(K key){
        //1.计算index
        int index = get_index(key);

        //2.判断
        if(listNodes[index] == null) return false;
        else return true;
    }

    public boolean containsValue(E val){

        int len = listNodes.length;
        //1,遍历数组
        for (int i = 0; i < len; i++) {
            //2.遍历链表
            for(ListNode<K,E> cur = listNodes[i]; cur != null;cur = cur.next){
                if(cur.val == val) return true;//找到了
            }
        }
        return false;//找不到
    }

    public void remove(K key){
        //1,获取index
        int index = get_index(key);

        //2.遍历链表
        ListNode<K,E> pre = null,cur = listNodes[index];
        //第一种请款，不存在节点
        if(cur == null) return;
        //第二种情况，删除头节点
        if(cur.key == key){
            listNodes[index] = cur.next;
            return;
        }
        //第三种情况，删除第二个 - 尾节点区间的节点
        while(cur != null){
            //找到了，删除
            if(cur.key == key){
                pre.next = cur.next;
                cur.next = null;
                return;
            }
            //继续遍历
            pre = cur;
            cur = cur.next;
        }

        //第四种情况：找不到key值
        //不用删除，不用处理
        size--;
    }

    //返回所有key值
    public Collection<K> entryKey(){
        Collection<K> collection = new ArrayList<>();

        //遍历数组
        for (int i = 0; i < listNodes.length; i++) {
            ListNode<K,E> cur = listNodes[i];
            while(cur != null) {
                collection.add(cur.key);
                cur = cur.next;
            }
        }
        return collection;
    }

    //获取大小
}
class Test{
    public static void main(String[] args) {
        MyHashMap<Integer,Integer> hash = new MyHashMap<>();

        //1.添加元素
        hash.put(1,1);
        hash.put(2,2);
        hash.put(3,3);

        //2.containsKey
        System.out.println(hash.containsKey(3));
        System.out.println(hash.containsKey(4));

        hash.put(3,4);

        //3.containsValue
        System.out.println(hash.containsValue(3));

        //get
        System.out.println(hash.get(1));
        System.out.println(hash.get(2));

        //getOrDefault
        System.out.println(hash.getOrDefault(4,3));

        //remove
        hash.remove(3);

        //entryKey
        Collection<Integer> collection = hash.entryKey();

        Object[] o = collection.toArray();
        for(Integer x : collection)
        {
            System.out.println("key:" + x + "--> val :" + hash.get(x));
        }
    }
}
